package com.mj.listen2._01_排序;

import com.mj.listen2._01_排序.cmp.Sort;

/**
 * 计数排序简单实现
 */
public class _09_CountingSort extends Sort<Integer> {
    @Override
    protected void sort() {
        // 1.找到数组中的最大值
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        }

        // 2.创建一个 max + 1 大小的临时数组
        int[] temp = new int[max + 1];
        // 对原始数组进行计数统计
        for (int i = 0; i < array.length; i++) {
            // temp的索引对应array中的元素，装的是array中值出现的次数
            temp[array[i]]++;
        }

        // 3.遍历 temp 得到排序的数组
        int index = 0;// 定义index指针，用于指向array下一次存储的索引
        for (int i = 0; i < temp.length; i++) {
            // i 在 array 中表示数组的值
            while (temp[i]-- > 0) {// 值 i 出现了几次
                // 给数组赋值
                array[index++] = i;
            }
        }
    }
}
